﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Per_pixel_OCR
{
    class DecisionNode
    {
        public DecisionTree Owner { get; private set; }
        public DecisionNode Parent { get; private set; }
        public Pixel[] Inputs { get; private set; }
        public int? Output { get; private set; }
        public double[] HistogramOutput { get; private set; }
        public int Level { get; private set; }
        public Feature SplitFeature { get; set; }
        public DecisionNode[] Branches { get; private set; }

        public bool IsRoot
        {
            get { return Parent == null; }
        }

        public bool IsLeaf
        {
            get { return Branches == null || Branches.Length == 0; }
        }

        public DecisionNode(DecisionTree owner, DecisionNode parent, Pixel[] inputs)
        {
            this.Owner = owner;
            this.Parent = parent;
            this.Inputs = inputs;

            this.Level = IsRoot ? 0 : this.Parent.Level + 1;
        }

        private Feature[] GetFeatureCandidates()
        {
            Feature[] rVal = new Feature[Parameters.UsedFeatureCountAtEveryNode];

            for (int i = 0; i < rVal.Length / 2; i++)
                rVal[i] = new Feature(FeatureType.MINUS);

            for (int i = rVal.Length/2; i < rVal.Length; i++)
                rVal[i] = new Feature(FeatureType.PLUS);     

            return rVal;
        }

        public DecisionNode[] Split()
        {
            Feature[] featureCandidates;
            Pixel[][][] partitions;
            int bestAttributeIndex;
            double bestScore;

            double entropy = Entropy(this.Inputs);

            int numClasses = Parameters.SelectedDigits.Length;
            double maxEntropy = Math.Log(numClasses, 2);
            double entropyThreshold = maxEntropy / 1000;

            if (entropy < entropyThreshold || this.Level > Parameters.MaxDepth)
            {
                this.Output = MostCommon(this.Inputs);
                this.HistogramOutput = GetHistogram(this.Inputs);
                this.Inputs = null;

                return null;
            }

            int counter = 0;

            do
            {
                featureCandidates = GetFeatureCandidates();

                double[] scores = new double[featureCandidates.Length];
                partitions = new Pixel[featureCandidates.Length][][];

                for (int i = 0; i < featureCandidates.Length; i++)
                {
                    scores[i] = ComputeGainRatio(this.Inputs, featureCandidates[i], out partitions[i], entropy);
                }

                bestAttributeIndex = scores.MaxIndex();
                bestScore = scores[bestAttributeIndex];

                counter++;
            }
            while (!(bestScore > entropyThreshold) && counter < 4);

            if (counter == 4)
            {
                this.Output = MostCommon(this.Inputs);
                this.HistogramOutput = GetHistogram(this.Inputs);
                this.Inputs = null;

                return null;
            }

            this.SplitFeature = featureCandidates[bestAttributeIndex];

            this.Branches = new DecisionNode[2];

            this.Branches[0] = new DecisionNode(this.Owner, this, partitions[bestAttributeIndex][0]);
            this.Branches[1] = new DecisionNode(this.Owner, this, partitions[bestAttributeIndex][1]);

            this.Inputs = null;

            return this.Branches;
        }

        private int MostCommon(Pixel[] pixels)
        {
            int[] frequencies = new int[Parameters.HistogramLength];

            for (int i = 0; i < pixels.Length; i++)
                frequencies[pixels[i].ClassID]++;

            return frequencies.MaxIndex();            
        }

        public double ComputeGainRatio(Pixel[] pixels, Feature feature, out Pixel[][] partitions, double currentEntropy)
        {
            double infoGain = currentEntropy - ComputeInfo(pixels, feature, out partitions);
            //double splitInfo = SplitInformation(partitions, this.Inputs.Length);

            //double gainRatio = splitInfo == 0 ? 0 : infoGain *splitInfo;

            return infoGain;
        }

        public double ComputeInfo(Pixel[] pixels, Feature feature, out Pixel[][] partitions)
        {
            partitions = new Pixel[2][];

            List<Pixel> tempPartitions0 = new List<Pixel>(pixels.Length);
            List<Pixel> tempPartitions1 = new List<Pixel>(pixels.Length);

            for (int i = 0; i < pixels.Length; i++)
            {
                bool result = pixels[i].ComputeFeature(feature); // false is left, true is right

                if (result == false)
                    tempPartitions0.Add(pixels[i]);
                else
                    tempPartitions1.Add(pixels[i]);
            }

            partitions[0] = tempPartitions0.ToArray();
            partitions[1] = tempPartitions1.ToArray();

            // Compute the information gain obtained by using
            // this current attribute as the next decision node.
            double info = 0;

            for (int i = 0; i < partitions.Length; i++)
            {
                double e = Entropy(partitions[i]);

                info += ((double)partitions[i].Length / this.Inputs.Length) * e;
            }

            return info;
        }

        public static double Entropy(Pixel[] pixels)
        {
            if (pixels.Length == 0)
                return 0;

            int[] frequencies = new int[Parameters.HistogramLength];
            double[] p = new double[Parameters.HistogramLength];

            for (int i = 0; i < pixels.Length; i++)
                frequencies[pixels[i].ClassID]++;

            for (int i = 0; i < frequencies.Length; i++)
                p[i] = (double)frequencies[i] / pixels.Length;

            double sum = 0;
            for (int i = 0; i < p.Length; i++)
                if (p[i] != 0) sum += p[i] * Math.Log(p[i], 2);

            return -1 * sum;
        }

        public static double SplitInformation(Pixel[][] partitions, int numTotalRecords)
        {
            double info = 0;

            for (int i = 0; i < partitions.Length; i++)
            {
                double p = (double)partitions[i].Length / numTotalRecords;
                if (p != 0)
                    info -= p * Math.Log(p, 2);
            }

            return info;
        }

        public DecisionNode PassToChild(Pixel p)
        {
            bool temp = p.ComputeFeature(this.SplitFeature);
           
            if (temp == false)
                return this.Branches[0];
            return this.Branches[1];
        }

        public double[] GetHistogram(Pixel[] inputs)
        {
            double[] rVal = new double[Parameters.HistogramLength];

            for (int i = 0; i < inputs.Length; i++)
            {
                rVal[inputs[i].ClassID]++;
            }

            for (int i = 0; i < rVal.Length; i++)
            {
                rVal[i] = rVal[i] / inputs.Length;
            }

            return rVal;
        }
    }
}
